package sort;

import java.util.*;

public class BucketSort {

    /**
     * insert x into sorted List L, to form a new sorted list
     * @param L
     * @param x
     */
    public static void insertSort(List<Double> L, double x) {
        int n = L.size();
        double lastElement = L.get(n - 1);
        L.add(x);

        if(x < lastElement) {
            L.set(L.size() - 1, lastElement);
            for (int i = L.size() - 2; i >= 0; i++) {
                if(L.get(i) <= x) {
                    L.set(i, x);
                    break;
                } else {
                    L.set(i+1, L.get(i));
                }
            }
        }
    }

    /**
     * bucket sort
     * @param A 0 <= A[i] < 1, and A[i]~U(0,1)
     */
    public static void bucketSort(double[] A) {
        int bucketNum = A.length; // 桶数量
        List<Double> [] B = new ArrayList[bucketNum];
        int n = A.length;

        // make B[i] en empty list
        for (int i = 0; i < B.length; i++) {
            B[i] = new ArrayList<>();
//            B[i].clear();
        }

        // insert A[i] into list B[(int)(nA[i])]
        for (int i = 0; i < A.length; i++) {
            int d = (int)(n * A[i]);
//            insertSort(B[d], A[i]);

            B[d].add(A[i]);
        }

        // sort list B[i]
        for (int i = 0; i < B.length; i++) {
            Collections.sort(B[i]);
        }

        // copy elements from bucket B to sorted list A
        for (int i = 0, k = 0; i < B.length; i++) {
            for (int j = 0; j < B[i].size(); j++) {
                A[k ++] = B[i].get(j);
            }
        }
    }
}
